package main.Q901_1000;

import java.util.*;

public class Q941_950 {
    public static void main(String[] args) {
        System.out.println("Question941：");
        System.out.println("Question942：");
        System.out.println("Question943：");
        System.out.println("Question944：");
        System.out.println("Question945：");
        System.out.println("Question946：验证栈序列");
        System.out.println("Question947：移除最多的同行或同列石头");
        System.out.println("Question948：");
        System.out.println("Question949：");
        System.out.println("Question950：按递增顺序显示卡牌");
    }
}

class Question946 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0;
        while (j < popped.length) {
            if (i < pushed.length && (stack.isEmpty() || stack.peek() != popped[j])) {//此时栈空或者栈顶元素不为弹出元素
                stack.add(pushed[i]);//入栈
                i++;
            } else if (stack.peek() == popped[j]) {//此时栈顶元的为弹出元素
                stack.pop();
                j++;
            } else if (i > pushed.length - 1 && stack.peek() != popped[j]) return false;//全部入栈后，栈顶元素不为弹出元素
        }
        return true;
    }
}

class Question947 {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        Map<Integer, Integer> parent = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int[] stone = stones[i];
            int x = stone[0] + 10000; //横坐标区别开纵坐标，加100000，不会有歧义
            while (x != parent.getOrDefault(x, x)) x = parent.get(x);
            int y = stone[1];
            if (!parent.containsKey(y)) parent.put(y, y);
            while (y != parent.get(y)) y = parent.get(y);
            if (x == y) continue;
            parent.put(x, y);
        }
        int left = 0; //取圈子数即可
        for (Map.Entry<Integer, Integer> entry : parent.entrySet()) {
            if (entry.getKey().equals(entry.getValue())) {
                left++;
            }
        }
        return n - left;
    }
}

class Question950 {
    public int[] deckRevealedIncreasing(int[] deck) {
        int N = deck.length;
        Deque<Integer> index = new LinkedList<>();
        for (int i = 0; i < N; ++i) {
            index.add(i);
        }
        int[] result = new int[N];
        Arrays.sort(deck);
        for (int card : deck) {
            result[index.pollFirst()] = card;
            if (!index.isEmpty()) {
                index.add(index.pollFirst());
            }
        }
        return result;
    }
}